数据结构 Tree DFS 和 BFS

深度优先遍历（DFS）和 广度优先遍历（BFS）

参考资料 二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）

深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。

广度优先遍历：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。

DFS：ABDECFG（前中后序） BFS：ABCDEFG（层序遍历）

DFS实现：

• 数据结构：栈
• 父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可

BFS实现：

• 数据结构：队列
• 父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可

带记忆的 DFS

二叉树中和为某一值的路径

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例: 给定如下二叉树，以及目标和 target = 22

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

解题，具体解释看注释，这里记忆功能的核心就是 temp

import java.util.ArrayList;

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        dfs(root, target);
        return ans;
    }
    
    final ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    // dfs 记忆功能关键就是对这个 temp 的理解
    final ArrayList<Integer> temp = new ArrayList<>();
    
    // 关键理解就是 dfs 的递归过程，每次递归都是到同一个方向的最后一个节点，它并不是 “同时进行” 的！！
    // 所以每次只需考虑同一条路径上的节点
    void dfs(TreeNode root,int target) {
        if (root == null) return;
        
        // 每次都得把当前节点丢进 temp
        temp.add(root.val);
        
        // 当根节点等于最后一个值时表示当前找到的这条路径是满足条件的
        if (root.right == null && root.left == null && root.val == target) {
            ans.add(new ArrayList<Integer>(temp));
        }
        
        dfs(root.left, target - root.val);
        dfs(root.right, target - root.val);
        // 在归的时候，移除当前 temp 最后一个节点
        temp.remove(temp.size() - 1);
    }
}

复制一颗二叉树

#include<cstdio>
#include<iostream>

struct treenode//结点的定义
{
    int data;
    treenode* left;
    treenode* right;
};

typedef treenode* Tree;

Tree CopyNode(Tree t)//复制结点t
{
    Tree newT = (Tree)malloc(sizeof(treenode));
    newT->data = t->data;
    newT->left = t->left;
    newT->right = t->right;
    return newT;
}

Tree CopyTree(Tree t)
{
    if(!t)
        return NULL;//树为空，直接返回NULL

    Tree newLeft = NULL,newRight = NULL,newTree = NULL;
    if(t->left)//左子树不为空则复制左子树
        newLeft = CopyTree(t->left);
    else
        newLeft = NULL;
    if(t->right)//右子树不为空则复制右子树
        newRight = CopyTree(t->right);
    else
        newRight = NULL;

    Tree NewTree = CopyNode(t);//复制左右子树的根结点
    NewTree->left = newLeft;
    NewTree->right = newRight;

    return NewTree;
}